﻿
using CSharpLibs.Annotations;

#pragma warning disable 0169
#pragma warning disable 0649
#pragma warning disable 0436

namespace System.Collections.Generic
{
	[Builtin, Container, Set, BuiltinImplementation]
	public sealed class HashSet<T> : Object, ISet<T>, ICollection<T>, IEnumerable<T>, IEnumerable
	{
		private int card;
		private int capacity;

		[MultiLocationField]
		private int allh;

		[MultiLocationField]
		private T allf;

		[BuiltinMethod, BuiltinSemantics("hashset_init")]
		public HashSet()
		{ ;}

		public HashSet(IEnumerable<T> collection)
		{
			IEnumerator<T> ev = collection.GetEnumerator();
			while(ev.MoveNext())
				this.Add(ev.Current);
		}

		[DoNotClearCollectionPosition]
		public bool Add(T item)
		{
			this.ReAllocateInternalTableAsNeeded();
			int matchpos = this.TablePosFor(item);

			if(this.GetHashAndValidForIndex(matchpos) < 0)
			{
				int hash = HashForStore(item);
				this.DoSetAdd(matchpos, hash, item);
				return true;
			}

			return false;
		}

		[BuiltinMethod, DoNotClearCollectionPosition, BuiltinSemantics("hashset_adddirect")]
		private void DoSetAdd(int pos, int hash, T value)
		{ ;}
		
		[BuiltinMethod, BuiltinSemantics("hashset_clear")]
		public void Clear()
		{ ;}

		public bool Contains(T item)
		{
			int matchpos = this.TablePosFor(item);
			return this.GetHashAndValidForIndex(matchpos) >= 0;
		}

		private bool ContainsAllElements(IEnumerable<T> other)
		{
			IEnumerator<T> ev = other.GetEnumerator();
			while(ev.MoveNext())
			{
				if(!this.Contains(ev.Current))
					return false;
			}
			return true;
		}

		public void CopyTo(T[] array)
		{
			int j = 0;
			for(int i = 0; i < this.capacity; ++i)
			{
				if(this.GetHashAndValidForIndex(i) >= 0)
					array[j++] = this.GetValueAtIndex(i);
			}
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			int j = arrayIndex;
			for(int i = 0; i < this.capacity; ++i)
			{
				if(this.GetHashAndValidForIndex(i) >= 0)
					array[j++] = this.GetValueAtIndex(i);
			}
		}

		public void ExceptWith(IEnumerable<T> other)
		{
			IEnumerator<T> ev = other.GetEnumerator();
			while(ev.MoveNext())
				this.Remove(ev.Current);
		}

		public Enumerator GetEnumerator()
		{ return new Enumerator(this); }

		public void IntersectWith(IEnumerable<T> other)
		{
			bool[] covered = new bool[this.capacity];
			
			IEnumerator<T> ev = other.GetEnumerator();
			while(ev.MoveNext())
			{
				int matchpos = this.TablePosFor(ev.Current);
				if(this.GetHashAndValidForIndex(matchpos) >= 0)
					covered[matchpos] = true;
			}

			this.RemoveAtFlags(covered);
		}

		public bool IsSubsetOf(IEnumerable<T> other)
		{
			bool[] covered = new bool[this.capacity];
			
			IEnumerator<T> ev = other.GetEnumerator();
			while(ev.MoveNext())
			{
				int matchpos = this.TablePosFor(ev.Current);
				if(this.GetHashAndValidForIndex(matchpos) >= 0)
					covered[matchpos] = true;
			}

			for(int i = 0; i < this.capacity; ++i)
			{
				if((this.GetHashAndValidForIndex(i) >= 0) && (!covered[i]))
					return false;
			}

			return true;
		}

		public bool IsSupersetOf(IEnumerable<T> other)
		{
			IEnumerator<T> ev = other.GetEnumerator();
			while(ev.MoveNext())
			{
				int matchpos = this.TablePosFor(ev.Current);
				if(this.GetHashAndValidForIndex(matchpos) < 0)
					return false;
			}

			return true;
		}

		public bool Overlaps(IEnumerable<T> other)
		{
			IEnumerator<T> ev = other.GetEnumerator();
			while(ev.MoveNext())
			{
				int matchpos = this.TablePosFor(ev.Current);
				if(this.GetHashAndValidForIndex(matchpos) >= 0)
					return true;
			}

			return false;
		}

		public bool Remove(T item)
		{
			int matchpos = this.TablePosFor(item);
			if(this.GetHashAndValidForIndex(matchpos) < 0)
				return false;

			this.RemoveAt(matchpos);
			return true;
		}

		public int RemoveWhere(Predicate<T> match)
		{
			bool[] remain = new bool[this.capacity];
			int count = 0;

			for(int i = 0; i < this.capacity; ++i)
			{
				if(this.GetHashAndValidForIndex(i) >= 0)
				{
					if(match(this.GetValueAtIndex(i)))
						++count;
					else
						remain[i] = true;
				}
			}

			this.RemoveAtFlags(remain);
			return count;
		}

		[BuiltinMethod, BuiltinSemantics("hashet_removeatdirect")]
		private void RemoveAt(int pos)
		{ ;}

		[BuiltinMethod, BuiltinSemantics("hashet_removeatflags")]
		private void RemoveAtFlags(bool[] flags)
		{ ;}

		public bool SetEquals(IEnumerable<T> other)
		{
			int count = 0;
			IEnumerator<T> ev = other.GetEnumerator();
			while(ev.MoveNext())
			{
				++count;

				int matchpos = this.TablePosFor(ev.Current);
				if(this.GetHashAndValidForIndex(matchpos) < 0)
					return false;
			}

			return count == this.card;
		}

		[DoNotClearCollectionPosition]
		void ICollection<T>.Add(T item)
		{
			this.ReAllocateInternalTableAsNeeded();
			int matchpos = this.TablePosFor(item);

			if(this.GetHashAndValidForIndex(matchpos) < 0)
			{
				int hash = HashForStore(item);
				this.DoSetAdd(matchpos, hash, item);
			}
		}

		IEnumerator<T> IEnumerable<T>.GetEnumerator()
		{ return new Enumerator(this); }

		IEnumerator IEnumerable.GetEnumerator()
		{ return new Enumerator(this); }

		internal T[] ToArray()
		{
			T[] res = new T[this.card];
			int j = 0;
			for(int i = 0; i < this.capacity; ++i)
			{
				if(this.GetHashAndValidForIndex(i) >= 0)
					res[j++] = this.GetValueAtIndex(i);
			}

			return res;
		}

		public void UnionWith(IEnumerable<T> other)
		{
			IEnumerator<T> ev = other.GetEnumerator();
			while(ev.MoveNext())
				this.Add(ev.Current);
		}

		public int Count
		{
			[BuiltinMethod, BuiltinSemantics("hashset_getcount")]
			get { return -1; }
		}

		[BuiltinMethod, DoNotClearCollectionPosition, BuiltinSemantics("hashset_gethvalid")]
		internal int GetHashAndValidForIndex(int i)
		{ return -1; }

		[BuiltinMethod, BuiltinSemantics("hashset_getvalue")]
		internal T GetValueAtIndex(int i)
		{ return default(T); }

		private static int HashForStore(T item)
		{
			if(item == null)
				return 0;
			
			int bhash = item.GetHashCode();
			return bhash & 0x7fffffff;
		}

		[DoNotClearCollectionPosition]
		private int TablePosFor(T item)
		{
			int hash;
			if(item == null)
				hash = 0;
			else
			{
				int bhash = item.GetHashCode();
				hash = bhash & 0x7fffffff;
			}

			int pos = hash % this.capacity;
			
			if(this.GetHashAndValidForIndex(pos) < 0)
				return pos;

			if((this.GetHashAndValidForIndex(pos) == hash) && EqualityComparer<T>.DefaultEquals(item, this.GetValueAtIndex(pos)))
				return pos;

			int i = (pos + 1) % this.capacity;
			while(true)
			{
				if(this.GetHashAndValidForIndex(i) < 0)
					return i;

				if((this.GetHashAndValidForIndex(i) == hash) && EqualityComparer<T>.DefaultEquals(item, this.GetValueAtIndex(i)))
					return i;

				i = (i + 1) % this.capacity;
			}
		}

		[BuiltinMethod, BuiltinSemantics("hashset_resizeasneeded"), DoNotClearCollectionPosition]
		private void ReAllocateInternalTableAsNeeded()
		{ ;}

		[Builtin, Enumerator]
		public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
		{
			[EnumeratorCollectionField]
			private HashSet<T> hset;

			private int index;

			internal Enumerator(HashSet<T> set)
			{
				this.hset = set;
				this.index = -1;
			}

			public void Dispose()
			{ ;}

			[EnumeratorAdvance]
			public bool MoveNext()
			{
				if(this.index < this.hset.capacity)
					this.index++;

				while(this.index < this.hset.capacity)
				{
					if(this.hset.GetHashAndValidForIndex(this.index) >= 0)
						return true;

					this.index++;
				}

				return false;
			}

			public T Current
			{
 				[EnumeratorGetterSimpleContainer]
				get { return this.hset.GetValueAtIndex(this.index); } 
			}

			object IEnumerator.Current
			{ get { return this.hset.GetValueAtIndex(this.index); } }

			void IEnumerator.Reset()
			{ this.index = -1; }
		}
	}
}

#pragma warning restore 0436
#pragma warning restore 0649
#pragma warning restore 0169
